package com.xiaoyu.linkedArray;

import java.util.ArrayDeque;

/**
 * @program: DS_and_A
 * @description: leetCode第二题:两数字相加
 *
 * 给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
 *
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 *
 * 你可以假设除了数字 0 之外，这两个数都不会以 0开头。
 *
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[7,0,8]
 * 解释：342 + 465 = 807.
 *
 * @author: YuWenYi
 * @create: 2021-05-10 09:49
 **/
public class AddTwoNumbers {
    //错误案例:将listNode转换成数字! 殊不知LeetCode早已看穿,用一个超级大的数字,哪怕使用Long也会出现无法转换异常..
    //因此不能将listNode转换成数字!
  /*  public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        Long num1 = parseToNum(l1);
        Long num2 = parseToNum(l2);
        long sum = num1+num2;
        StringBuilder sb = new StringBuilder(""+sum);
        StringBuilder reverse = sb.reverse();

        ListNode node = new ListNode();
        ListNode res = node;
        for (int i = 0; i < reverse.length(); i++) {
            if (i != reverse.length()-1){
                node.next = new ListNode();
            }
            node.val = Integer.parseInt(String.valueOf(reverse.charAt(i)));
            node = node.next;
        }
        return res;
    }
    public Long parseToNum(ListNode node){
        ArrayDeque<String> stack = new ArrayDeque<>();
        while (node.next!=null){
            stack.push(String.valueOf(node.val));
            node = node.next;
        }
        stack.push(String.valueOf(node.val));

        StringBuilder sb = new StringBuilder("");
        while (!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return Long.parseLong(sb.toString());
    }*/


    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0); //root用来保存头结点,用以返回结果
        ListNode pointer = root;   //指针用来链表的移动
        int carry = 0;
        while (l1!=null || l2!=null || carry!=0){ //carry!=0非常重要,如果顶位有进位,就靠它来进入循环然后加上去
            int n1 = l1 == null ? 0 : l1.val;
            int n2 = l2 == null ? 0 : l2.val;
            int bitSum = carry + n1 + n2;
            carry = bitSum / 10;

            pointer.next = new ListNode(bitSum % 10);
            pointer = pointer.next;

            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        return root.next;
    }

    public static void main(String[] args) {
        AddTwoNumbers numbers = new AddTwoNumbers();

        ListNode l1 = new ListNode(5,new ListNode(4,
                new ListNode(3)));  //345
        ListNode l2 = new ListNode(6,new ListNode(5,
                new ListNode(7,new ListNode(9))));

        ListNode sum = numbers.addTwoNumbers(l1, l2);//10001
        while (sum.hasNext()){
            System.out.print(sum.val+",");
            sum = sum.next;
        }
        System.out.print(sum.val);
    }
}
